package main

// 79. 单词搜索
func main() {
	board := [][]byte{
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'C', 'S'},
		{'A', 'D', 'E', 'E'},
	}
	word := "ABCCED"
	b := exist(board, word)
	println(b)
}

func exist(board [][]byte, word string) bool {
	if len(board) == 0 || len(board[0]) == 0 {
		return false
	}
	X := len(board)
	Y := len(board[0])
	wordLen := len(word)

	investMap := make(map[int]bool)
	turnRoundSlice := [][]int{
		{0, 1}, {1, 0}, {0, -1}, {-1, 0},
	}

	var dfs func(i, j int, wordIdx int) bool
	dfs = func(i, j int, wordIdx int) bool {
		if i < 0 || j < 0 || i >= X || j >= Y {
			return false
		}
		char := word[wordIdx]
		uniqKey := i*Y + j
		if investMap[uniqKey] { // 访问过了，return false
			return false
		}
		if char == board[i][j] && wordIdx == wordLen-1 { // 不相等，return false
			return true
		}
		if char != board[i][j] {
			return false
		}
		// 这下相等了，看看儿子们顶不顶得住
		investMap[uniqKey] = true
		for _, turnRound := range turnRoundSlice {
			if dfs(i+turnRound[0], j+turnRound[1], wordIdx+1) {
				return true
			}
		}
		investMap[uniqKey] = false

		return false
	}

	for i := 0; i < X; i++ {
		for j := 0; j < Y; j++ {
			if dfs(i, j, 0) {
				return true
			}
		}
	}

	return false
}

func exist2(board [][]byte, word string) bool { // 这个写法更快？
	var has bool
	wordBytes := []byte(word)
	wordBytesLen := len(wordBytes)
	if len(board) == 0 || len(board[0]) == 0 {
		return false
	}
	height := len(board)
	length := len(board[0])

	visited := make([][]bool, height)
	for i := range visited {
		visited[i] = make([]bool, length)
	}

	var dfs func(i, j, idx int) bool
	dfs = func(i, j, idx int) bool {
		// 上下左右回溯，记录访问状态，注意边界，进来直接处理边界
		if (i < 0 || i > height-1) || (j < 0 || j > length-1) || visited[i][j] {
			return false
		}
		if idx == wordBytesLen-1 && board[i][j] == wordBytes[idx] {
			return true
		}
		if board[i][j] == wordBytes[idx] {
			visited[i][j] = true
			topRes := dfs(i-1, j, idx+1)
			rightRes := dfs(i, j+1, idx+1)
			bottomRes := dfs(i+1, j, idx+1)
			leftRes := dfs(i, j-1, idx+1)
			visited[i][j] = false
			if topRes || rightRes || bottomRes || leftRes {
				return true
			}
		}
		return false
	}

	for h := 0; h < height; h++ {
		for l := 0; l < length; l++ {
			has = dfs(h, l, 0)
			if has {
				return has
			}
		}
	}

	return has
}

// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
//单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
//
//示例 1：
//
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
//输出：true
//示例 2：
//
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
//输出：true
//示例 3：
//
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
//输出：false
//
//提示：
//
//m == board.length
//n = board[i].length
//1 <= m, n <= 6
//1 <= word.length <= 15
//board 和 word 仅由大小写英文字母组成
//
//进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
